The present invention concerns a coding device, a coding method, a decoding device and method and systems implementing them.
It applies equally well to the coding of data representing a physical quantity, to the coding of data in the form of codes able to modulate a physical quantity, to the decoding of data modulated signals, and to the decoding of data representing physical quantities. These data can, for example, represent images, sounds, computer data, electrical quantities or stored data.
The invention finds an application in the field of convolutional codes. When the latter are used for implementing an iterative decoding, these codes are greatly improved when their coders contain a permutation device. In this case, they are normally referred to as xe2x80x9cturbocodesxe2x80x9d and the corresponding iterative decoder is referred to as a xe2x80x9cturbodecoderxe2x80x9d.
On these subjects, documents which serve as a reference are, on the one hand, the article by Messrs. C. BERROU, A. GLAVIEUX and P. THITIMAJSHIMA entitled xe2x80x9cNear Shannon limit error-correcting coding and decoding turbocodesxe2x80x9d published with the reports on the conference xe2x80x9cICC""93xe2x80x9d, 1993, pages 1064 to 1070, and on the other hand the article by Messrs. C. BERROU and A. GLAVIEUX entitled xe2x80x9cNear Optimum error-correcting coding and decoding: turbo-codesxe2x80x9d published by IEEE Transactions on Communication, Volume COM-44, pages 1261 to 1271, in October 1996.
However, the formation of permutation devices is as far from being perfectly mastered. In general this device uses square or rectangular matrices in which one line after another is written and one column after another is read. These matrices are generally very large, for example 256xc3x97256 in size.
A turbocoder with an efficiency of ⅓ can be considered to be a pair of convolutional systematic coders using divisor polynomials. The first coder produces a check sequence from the sequence of symbols to be coded u and the second coder produces a check sequence from an interleaved sequence u* obtained by interleaving the sequence u. In this context, the return to zero of the two coders, simultaneously, is a classic problem.
A first manner of resolving this was described in the publication xe2x80x9cFrame oriented convolutional turbo-codesxe2x80x9d, (C. BERROU et al.), Electronics Letters, Volume 32, No. 15, Jul. 18, 1996 p. 1362-1364, Stevenage, Herts, Great Britain.
Let the divisor polynomial of a turbocoder, that is to say of each elementary coder, be g(x). Let the degree of the polynomial g(x) be m and N0 the smallest integer such that g(x) is a divisor of the polynomial xN0+1. Let also n be a multiple of N0: n=M N0.
In order to disclose the content of this publication, the sequence of symbols to be coded will be represented as a sequence of polynomials u(x)=xcexa3i=0 to nxe2x88x921 uixi. Thus each polynomial u(x) contains n binary symbols to be coded.
Let then u(x) be written as
u(x)=xcexa3j=0 to N0xe2x88x921sj(xN0)xi.
where each polynomial sj(x) has a degree Mxe2x88x921.
With regard to FIG. 1, it will be understood that this set of writings can be represented as follows:
in a table 101 having N0 columns, the symbols ui of the sequence u, are entered, row by row, from left to right and starting from the highest line and going towards the lowest line in the table;
the polynomials Sj(x) are polynomials whose coefficients of increasing rankings are the symbols which are situated in the jth column in the table, entered, in order, from top to bottom.
Let S*j(x) then be another polynomial of degree Mxe2x88x921 obtained from Sj(x) by permutation of its coefficients. For different values of j, the permutations producing S*j(x) from Sj(x) can be different.
In the table 101 considered above, this amounts to stating that the coefficients of the polynomial Sj*(x) are those of the jth column in the table, but in a different order from the coefficients of the polynomial Sj(x).
If the table 102 corresponding to the polynomials Sj*(x) is written in the same way as the table 101 corresponds to the polynomials Sj(x), by juxtaposing the last line in the table 101 and the first in the table 102, is found that each coefficient which is situated in the jth column in the table 101 is situated in the jth column in the table 102.
Let then u*(x)=xcexa3j=0 to N0xe2x88x921s*j(xN0)xi be written and let:
i uu*(x)=u(x)+xnu*(x) be defined.
It is easy to show that uu*(x) is divisible by g(x). Therefore the coding of u(x) as v=[u, uu*/g] is possible with an exact division. The efficiency R of this coding is then given by R=nl(3nxe2x88x92m).
A second way of resolving the problem of the return to zero of the coder has been found by the inventors and is summarised below.
Let g(x) be the divisor polynomial of a turbocoder, that is to say of each coder. Let m be the degree of the polynomial g(x) and N0 the smallest integer such that g(x) is a divisor of the polynomial xN0+1. For reasons described below, g(x) is considered to be a xe2x80x9cpolynomial without squarexe2x80x9d and this means that N0 is an odd number.
Let also n be an odd multiple of N0: n=M N0.
A sequence of symbols u, of length nxe2x80x2=nxe2x88x92m, then has a polynomial representation u(x), of degree nxe2x88x92mxe2x88x921, with binary coefficients, and this polynomial u(x) is precoded as:
a(x)=u(x)+xcexa3i=nxe2x88x92mnxe2x88x921aixi
where the m symbols ai are chosen so that a(x) is a multiple of g(x). In consequence of this precoding, if a(x) is a multiple of g(x), then a*(x)=a(xe) modulo xn+1 is also a multiple of g(x) for any value of e which is a power of 2.
In the remainder of the description, this type of interleaver and, by extension, the type of turbocoders which implement them, is called xe2x80x9cx to xexe2x80x9d.
Here it is necessary to consider that g(x) has no multiple factor because, in general, a*(x) has the guarantee of being divisible solely by the irreducible factors of g(x).
The coded version of u is then given by v=[a, ah1/g, a*h2/g] where all the components are polynomials, and where, in particular, a*h2/g is also a polynomial, by virtue of the definition of a* and the choice of e as a power of 2.
The present invention aims to exploit conjointly the advantages of the teachings of the approaches mentioned above.
To this end, according to a first aspect, the present invention relates to a coding method, characterised in that: 1/ it takes into account:
a xe2x80x9cpolynomial without squarexe2x80x9d g(x),
N0, the smallest integer such that g(x) is a divisor of the polynomial xN0+1;
n, an odd multiple of N0;
a sequence u of n symbols ui to be coded; and
e, a power of 2 different from 1, for which the residue of e modulo N0 is equal to 1,
2/ it includes:
an operation of forming a so-called xe2x80x9cconcatenatedxe2x80x9d sequence uu* consisting successively, on the one hand, of the sequence of symbols u, having n symbols, and on the other hand a sequence of symbols u* defined by its polynomial representation, u*(x)=u(xe) modulo xn+1,
an operation of coding the concatenated sequence, including at least one division of the concatenated sequence uu* by the polynomial g(x) in order to form a so-called xe2x80x9ccheckxe2x80x9d sequence.
Thus the present invention consists of using, as a specific interleaver, in the coding scheme disclosed in the publication by C. BERROU et al., interleavers identical to those used by the inventors and presented above, of the type xe2x80x9cx to xexe2x80x9d, for which the residue of e modulo N0 is equal to 1.
The advantages of the present invention are as follows:
It describes a specific non-trivial way for implementing the idea of the publication by C. BERROU;
provision is made for the regular structure of the interleaver which is the object of the present invention to have favourable effects on the type of residual error after decoding;
implementation of the invention is particularly simple since merely the knowledge of the values of n and e suffices.
According to particular characteristics, the coding method to which the present invention relates, and as briefly disclosed above, includes an operation of transmitting the sequence to be coded u and the check sequence resulting from the operation of coding the concatenated sequence.
By virtue of these provisions, the transmitted sequence can be received, even if the transmission channel used is relatively noisy.
According to particular characteristics, the coding method to which the present invention relates, and as briefly disclosed above, includes an operation of transmitting the sequence to be coded u and part of the check sequence resulting from the operation of coding the concatenated sequence.
By virtue of these provisions, the efficiency of the coding method is improved.
According to a second aspect, the present invention relates to a decoding method, characterised in that:
1/ it takes into account:
a xe2x80x9cpolynomial without squarexe2x80x9d g(x),
N0, the smallest integer such that g(x) is a divisor of the polynomial xN0+1;
n, an odd multiple of N0;
e, a power of 2 different from 1, for which the residue of e modulo N0 is equal to 1,
2/ it includes an operation of receiving signals representing:
a coded sequence u of n symbols ui; and
the result of the division by g(x) of a so-called xe2x80x9cconcatenatedxe2x80x9d sequence uu* consisting successively, on the one hand, of the sequence of symbols u, including n symbols, and on the other hand a sequence of symbols u* defined by its polynomial representation, u*(x)=u(xe) modulo xn+1,
3/ it includes a decoding operation including the use of the polynomial g(x).
According to a third aspect, the present invention relates to a coding device, characterised In that it has a processing means adapted:
1/ to take into account:
a xe2x80x9cpolynomial without squarexe2x80x9d g(x),
N0, the smallest integer such that g(x) is a divisor of the polynomial xN0+1;
n, an odd multiple of N0;
a sequence u of n symbols ui to be coded; and
e, a power of 2 different from 1, for which the residue of e modulo N0 is equal to 1,
2/ to form a so-called xe2x80x9cconcatenatedxe2x80x9d sequence uu* consisting successively, on the one hand, of the sequence of symbols u, including n symbols, and on the other hand a sequence of symbols u* defined by its polynomial representation, u*(x)=u(xe) modulo xn+1,
3/ to code the concatenated sequence by effecting at least one division of the concatenated sequence uu* by the polynomial g(x) in order to form a so-called xe2x80x9ccheckxe2x80x9d sequence.
According to a fourth aspect, the present invention relates to a decoding device, characterised in that:
1/ it has a processing means to take into account:
a xe2x80x9cpolynomial without squarexe2x80x9d g(x),
N0, the smallest integer such that g(x) is a divisor of the polynomial xN0+1;
n, an odd multiple of N0;
e, a power of 2 different from 1, for which the residue of e modulo N0 is equal to 1,
2/ it has a means of receiving signals representing:
a coded sequence u of n symbols ui; and
the result of the division by g(x) of a so-called xe2x80x9cconcatenatedxe2x80x9d sequence uu* consisting successively, on the one hand, of the sequence of symbols u, including n symbols, and on the other hand a sequence of symbols u* defined by its polynomial representation, u*(x)=u(xe) modulo xn+1,
3/ the processing means is adapted to decode the sequence u using the polynomial g(x).
The invention also relates to:
an information storage means which can be read by a computer or a microprocessor storing instructions of a computer program, characterised in that it makes it possible to implement the method of the invention as briefly disclosed above, and
a partially or totally removable information storage means which can be read by a computer or a microprocessor storing instructions of a computer program, characterised in that it makes it possible to implement the method of the invention as briefly disclosed above.
The invention also relates to:
a device for processing signals representing speech, which includes a device as briefly disclosed above,
a data transmission device having a transmitter adapted to implement a packet transmission protocol, which includes a device as briefly disclosed above,
a data transmission device having a transmitter adapted to implement the ATM (Asynchronous Transfer Mode) packet transmission protocol, which includes a device as briefly disclosed above,
the data transmission device having a transmitter adapted to implement the packet transmission protocol on a network of the ETHERNET (registered trade mark) type,
a network station, which has a device as briefly disclosed above,
a data transmission device including a transmitter transmitting over a wireless channel, which includes a device as briefly disclosed above, and
a device for processing sequences of signals representing at most one thousand binary data, which includes a device as briefly disclosed above.
Since these coding and decoding devices, these coding and decoding methods and these signal processing, data transmission and sequence processing devices and this network have the same particular characteristics and the same advantages as the coding method as briefly disclosed above, these particular characteristics and these advantages are not repeated here.